home *** CD-ROM | disk | FTP | other *** search
/ TPUG - Toronto PET Users Group / TPUG Users Group CD / TPUG Users Group CD.iso / AMIGA / AMICUS / AMICUS02.ADF / Asm / bsearch.asm < prev    next >
Assembly Source File  |  1989-05-30  |  6KB  |  172 lines
  1.  
  2. ;[70167,2216]
  3. ;BSEARC.ASM                15-Dec-85 5910               1
  4. ;
  5. ;    Keywords: BINARY SEARCH ASSEMBLER UTILITY
  6. ;    
  7. ;    The assembler source code to implement the Unix System V bsearch() function
  8. ;    that does a binary search on a table and returns the location of the sought
  9. ;    after data.  A companion to the qsort() function that sorts the data in a
  10. ;    table.  Bsearch.asm contains its own documentation as comments at the top
  11. ;    of the file.
  12. ;    
  13. ;    
  14. ;
  15.        RORG    0
  16.        XDEF    _bsearch
  17. *------------------------------------------------------------------------
  18. * A 68000 assembler implementation of the UNIX System V bsearch() function.
  19. * bsearch - binary search algorithm.
  20. * bsearch is a binary search routine generalized from Knuth (6.2.1) 
  21. * algorithm B.  It returns a pointer into a table indicating where a
  22. * datum may be found.  The table must be previously sorted in increasing
  23. * order according to the provided comparison function.  (See qsort.asm for
  24. * how to do this.)
  25. * bsearch should be declared in your C program as follows:
  26. *    extern char *bsearch();
  27. * and called as: (assuming location is a variable of type pointer to element)
  28. * location=(ELEMENT *)bsearch((char *) key, (char *) base, nel, 
  29. *                             sizeof(*key),compar);
  30. * where:
  31. *  unsigned nel;
  32. *  int (*compar) ();
  33. * and
  34. *  key points to the datum to be sought in the table.
  35. *  base points to the element at the base of the table, (i.e. &table[0])
  36. *  nel is the number of elements in the table.
  37. *  compar is the name of the comparison function (see qsort.asm), which is
  38. *  called with two arguments that point to the elements being compared.
  39. *  The function must return an integer less than, equal to, or greater than
  40. *  zero according as the first argument is to be considered less than, equal
  41. *  to, or greater than the second.  NOTE: in Lattice C the function compar
  42. *  must be declared extern before it is defined to insure proper argument
  43. *  passing orders.
  44. * Diagnostics:
  45. *  A NULL pointer is returned if the key cannot be found in the table.
  46. * Notes:
  47. *  the comparison function does not need to compare every byte, so arbitrary
  48. *  data may be contained in the elements in addition to the values being
  49. *  compared.
  50. *------------------------------------------------------------------------
  51. _bsearch:
  52.        link    a6,#0                   * link to caller and 
  53.        movem.l d4-d7/a2-a5,-(sp)       * save registers for restoration.
  54.        movea.l 8(a6),a5                * data to be sought in table.
  55.        movea.l 12(a6),a4               * base of the table.
  56.        move.l  20(a6),d7               * size of table elements.
  57.        movea.l 24(a6),a3               * get address of user's compar func.
  58.        move.l  d7,d0
  59.        add.l   d7,d0
  60.        move.l  d0,d6
  61.        move.l  16(a6),d0               * number of elements in table.
  62.        subq.l  #1,d0                   * elements run from 0 to n-1.
  63.        move.l  d0,-(sp)                * compute the size of the table in
  64.        move.l  d7,-(sp)                * bytes= number_elements * table_size
  65.        jsr     unsgmul
  66.        addq.l  #8,sp
  67.        add.l   a4,d0                   * add base address to size
  68.        movea.l d0,a2                   * a2 now points to the end of table
  69. BL1:
  70.        cmpa.l  a4,a2                   * make sure table is non-empty.
  71.        bcs.l   BL2                     * i.e. start address <> end address
  72.        move.l  d6,-(sp)                * calculate the mid point element's
  73.        move.l  a2,d0                   * address and leave it on the stack
  74.        sub.l   a4,d0
  75.        move.l  d0,-(sp)
  76.        jsr     unsgdiv
  77.        addq.l  #8,sp
  78.        move.l  d0,-(sp)
  79.        move.l  d7,-(sp)
  80.        jsr     unsgmul
  81.        addq.l  #8,sp
  82.        add.l   a4,d0
  83.        move.l  d0,d5
  84.        move.l  d5,-(sp)
  85.        move.l  a5,-(sp)                * along with the sought data's addr.
  86.        jsr     (a3)                    * call the user's compar function.
  87.        addq.l  #8,sp
  88.        move.l  d0,d4
  89.        tst.l   d4                      * are they equal?  (is d4=d0=0?)
  90.        bne.s   BL4                     * recomputed midpoint and retry.
  91.        move.l  d5,d0                   * done
  92.        bra.s   BL8
  93. BL4:
  94.        tst.l   d4                      * recompute the midpoint by
  95.        bge.s   BL5                     * either moving the ending address
  96.        move.l  d5,d0                   * of the table, (in a2) 
  97.        sub.l   d7,d0
  98.        movea.l d0,a2
  99.        bra.s   BL1
  100. BL5:
  101.        move.l  d5,d0                   * or the starting address ,(in a4)
  102.        add.l   d7,d0
  103.        movea.l d0,a4
  104. BL6:
  105.        bra.s   BL1                     * and try the comparison again.
  106. BL2:
  107.        moveq.l #0,d0                   * return 0 (NULL pointer) to signify
  108. *                                      * data not found in table.
  109. BL8:
  110.        movem.l (sp)+,a5-a2/d7-d4
  111.        unlk    a6
  112.        rts
  113. *
  114. * support routines to do unsigned multiplication and division
  115. *
  116. unsgmul:
  117.          lea      4(sp),a0
  118.          move.w   (a0)+,d0
  119.          move.l   8(sp),d1
  120.          mulu     d1,d0
  121.          swap     d1
  122.          mulu     (a0),d1
  123.          add.w    d1,d0
  124.          swap     d0
  125.          clr.w    d0
  126.          move.w   (a0),d1
  127.          mulu     10(sp),d1
  128.          add.l    d1,d0
  129.          move.l   d0,-2(a0)
  130.          rts
  131. unsgdiv:
  132.          lea      4(sp),a0
  133.          movem.l  d2-d3,-(sp)
  134.          move.l   (a0),d0
  135.          move.l   d0,d2
  136.          move.l   16(sp),d1
  137.          move.l   d1,d3
  138.          cmpi.l   #$10000,d1
  139.          bge.s    adjust
  140.          clr.w    d0
  141.          swap     d0
  142.          divu     d1,d0
  143.          move.w   d0,d3
  144.          move.w   d2,d0
  145.          divu     d1,d0
  146.          swap     d0
  147.          move.w   d3,d0
  148.          swap     d0
  149.          bra.s    fini
  150. adjust:
  151.          lsr.l    #1,d0
  152.          lsr.l    #1,d1
  153.          cmpi.l   #$10000,d1
  154.          bge.s    adjust
  155.          divu     d1,d0
  156.          andi.l   #$FFFF,d0
  157.          move.l   d3,d1
  158.          swap     d1
  159.          mulu     d0,d1
  160.          swap     d1
  161.          clr.w    d1
  162.          mulu     d0,d3
  163.          add.l    d3,d1
  164.          cmp.l    d1,d2
  165.          bge.s    fini
  166.          subq.l   #1,d0
  167. fini:
  168.          move.l   d0,(a0)
  169.          movem.l  (sp)+,d3-d2
  170.          rts
  171.  
  172.